package Heap;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;


/**
 * P506 相对名次
 * */
public class P506 {
    public static void main(String[] args) {
        P506Test02 p506Test02=new P506Test02();
        int[] a={10,3,8,9,4};

        String[] s=p506Test02.findRelativeRanks(a);
        for(int i=0;i<s.length;i++){
            System.out.println(s[i]);
        }
    }
}
/**
 * 利用包装类，然后进行比较实现
 * */
class MyStruct {
    int tag;
    int num;

    public MyStruct(int tag, int num) {
        this.tag = tag;
        this.num = num;
    }
}

class P506Test01 {
    public String[] findRelativeRanks(int[] score) {
        PriorityQueue<MyStruct> queue = new PriorityQueue<>((a, b) -> b.num - a.num);
        for (int i = 0; i < score.length; i++) {
            queue.add(new MyStruct(i, score[i]));
        }

        String[] result = new String[score.length];
        int rank = 1;
        while (!queue.isEmpty()) {
            MyStruct ms = queue.poll();
            if (rank == 1) {
                result[ms.tag] = "Gold Medal";
            } else if (rank == 2) {
                result[ms.tag] = "Silver Medal";
            } else if (rank == 3) {
                result[ms.tag] = "Bronze Medal";
            } else {
                result[ms.tag] = "" + rank;
            }
            rank++;
        }
        return result;
    }
}

/**
 * 排序+哈希表
 * 哈希表存下标，找到之后，方便找下标
 * 排序使用快排
 * */

class P506Test02{

    private Map<Integer,Integer> map=new HashMap<>();

    public String[] findRelativeRanks(int[] score) {
        for(int i=0;i<score.length;i++){
            map.put(score[i],i);
        }

        Arrays.sort(score);
        String[] s = new String[score.length];
        int length=score.length;
        int rank=1;
        for(int i=length-1;i>=0;i--){
            int j=map.get(score[i]);

            if(i== length-1){
                s[j]="Gold Medal";
            }
            else if(i==length-2){
                s[j]="Silver Medal";
            }
            else if(i==length-3){
                s[j]="Bronze Medal";
            }
            else{
                s[j]=""+rank;
            }
            rank++;
        }
        return s;
    }
}